package com.tsystems.school;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: victorn
 * Date: 8/15/11
 * Time: 12:03 AM
 * To change this template use File | Settings | File Templates.
 */
public class MyAvlTree {


    private Node root;
    private int size;
    List<Comparable> items;

    /**
     * Construct the tree.
     */
    public MyAvlTree() {
        root = null;
        size = 0;
    }

    /**
     * Insert into the tree; duplicates are ignored.
     *
     * @param node the item to put.
     */
    public void put(Comparable node) {
        root = put(node, root);
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private Node put(Comparable val, Node node) {
        if (node == null) {

            size++;
            node = new Node(val, null, null);

        } else if (val.compareTo(node.getValue()) < 0) {

            node.setLeft(put(val, node.getLeft()));

            if (height(node.getLeft()) - height(node.getRight()) == 2)

                if (val.compareTo(node.getLeft().getValue()) < 0) {
                    node = simpleLeftRotate(node);
                } else {
                    node = doubleLeftRotate(node);
                }

        } else if (val.compareTo(node.getValue()) > 0) {

            node.setRight(put(val, node.getRight()));

            if (height(node.getRight()) - height(node.getLeft()) == 2) {

                if (val.compareTo(node.getRight().getValue()) > 0) {
                    node = simpleRightRotate(node);
                } else {
                    node = doubleRightRotate(node);
                }
            }

        }

        node.setHeight(max(height(node.getLeft()), height(node.getRight())) + 1);

        return node;
    }

    private int height(Node node) {
        return (node == null) ? -1 : node.getHeight();
    }

    private int max(int val1, int val2) {
        return (val1 > val2) ? val1 : val2;
    }

    private Node simpleLeftRotate(Node node) {
        Node temp = node.getLeft();

        node.setLeft(temp.getRight());
        temp.setRight(node);

        node.setHeight(max(height(node.getLeft()), height(node.getRight())) + 1);
        temp.setHeight(max(height(temp.getLeft()), node.getHeight()) + 1);

        return temp;
    }

    private Node simpleRightRotate(Node node) {
        Node temp = node.getRight();

        node.setRight(temp.getLeft());
        temp.setLeft(node);

        node.setHeight(max(height(node.getLeft()), height(node.getRight())) + 1);
        temp.setHeight(max(height(temp.getRight()), node.getHeight()) + 1);

        return temp;
    }

    private Node doubleLeftRotate(Node node) {
        node.setLeft(simpleRightRotate(node.getLeft()));

        return simpleLeftRotate(node);
    }

    private Node doubleRightRotate(Node node) {
        node.setRight(simpleLeftRotate(node.getRight()));
        return simpleRightRotate(node);
    }

    private void toList(Node node) {
        if (node != null) {
            toList(node.getLeft());
            items.add(node.getValue());
            toList(node.getRight());
        }
    }

    public List<Comparable> toList() {
        if (isEmpty()) {
            return new ArrayList<Comparable>();
        } else {
            items = new ArrayList<Comparable>();
            toList(root);
            return items;
        }


    }

    public Node getRoot() {
        return root;
    }


}
